package test;

public class InterviewRoundOne {

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.insert(3);
        linkedList.insert(1);
        linkedList.insert(2);
        linkedList.insert(3);
        linkedList.insert(4);

        ListNode head = linkedList.delDuplication(linkedList.getHead());
        System.out.print(head.val + "->");
        ListNode tmp = head;
        while (tmp != null){
            tmp = tmp.next;
            if(tmp != null) {
                System.out.print(tmp.val + "->");
            }
        }
    }

}

class LinkedList{

    // 链表头节点
    private ListNode head;

    public LinkedList(){
        this.head = null;
    }

    public ListNode getHead(){
        return head;
    }

    public void insert(int val){
        ListNode newNode = new ListNode(val);
        if(head == null){
            head = newNode;
        }else{
            ListNode cur = head;
            while (cur.next != null){
                cur = cur.next;
            }
            cur.next = newNode;
        }
    }

    public ListNode delDuplication(ListNode head){
        ListNode tmp = head;
        ListNode pre = null;
        while (tmp != null){
            ListNode next = tmp.next;
            if(next !=null && tmp.val == next.val){
                ListNode delNode = tmp;
                int val = delNode.val;
                while (delNode!=null && delNode.val == val){
                    next = delNode.next;
                    delNode = next;
                }
                if(pre == null){
                    head = next;
                }else{
                    pre.next = next;
                }
                tmp = next;
            }else{
                pre = tmp;
                tmp = tmp.next;
            }
        }
        return head;
    }
}

class ListNode{
    int val;
    ListNode next;

    public ListNode(int val){
        this.val = val;
        this.next = null;
    }
}